class Solution:
    """这个不对,不应该是二分的"""
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        elif n == 3:
            return 2
        return self.search(n)

    def search(self, n):
        if n <= 4:
            return n
        if n % 2 == 0:
            return self.search(n // 2) ** 2
        else:
            return self.search(n // 2) * self.search(n // 2 + 1)


class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        elif n == 3:
            return 2
        if n % 3 == 0:
            return 3 ** (n // 3)
        elif n % 3 == 1:
            return 3 ** (n // 3 - 1) * 4
        else:
            return 3 ** (n // 3) * 2


a = Solution()
print(a.integerBreak(4))
print(a.integerBreak(10))
print(a.integerBreak(8))
